package com.heima.leetcode.practice;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * leetcode 15. 三数之和
 *
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/18 10:19
 */
public class E15 {

    /**
     * <h3>方法一：dfs递归加回溯，转变为两数之和</h3>
     *
     * @param nums nums数组
     * @return 满足条件的结果集合
     */
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        dfs(3, result, nums, new LinkedList<Integer>(), 0, 0, nums.length - 1);
        return result;
    }

    /**
     * dfs递归实现
     *
     * @param n              几数之和
     * @param result         结果集合
     * @param nums           数组
     * @param currentCombine 当前组合
     * @param target         目标值
     * @param begin          开始下标（包含）
     * @param end            结束下标（包含）
     */
    private void dfs(int n,
                     List<List<Integer>> result,
                     int[] nums,
                     LinkedList<Integer> currentCombine,
                     int target,
                     int begin,
                     int end) {
        // 1、递归结束条件：已经转变为了两数之和
        if (n == 2) {
            //  需要while循环，因为要找出所有满足条件组合
            while (begin < end) { // 相等的时候除外，因为一个元素只能选一次
                int currSum = nums[begin] + nums[end]; // 当前两数之和
                if (currSum < target) {
                    begin++;
                } else if (currSum > target) {
                    end--;
                } else {
                    // 满足条件的组合加到结果集合中
                    currentCombine.push(nums[begin]);
                    currentCombine.push(nums[end]);
                    result.add(new ArrayList<>(currentCombine));
                    // 回溯
                    currentCombine.pop();
                    currentCombine.pop();
                    // 移动下标
                    begin++;
                    end--;
                    // 跳过重复元素
                    while (begin < end && nums[begin] == nums[begin - 1]) {
                        begin++;
                    }
                    while (begin < end && nums[end] == nums[end + 1]) {
                        end--;
                    }
                }
            }
        }
        // 2、当前层递归，用for循环选取一个数定下来
        for (int k = begin; k <= end - n + 1; k++) {
            // 剪枝
            if (k > begin && nums[k] == nums[k - 1]) continue;
            currentCombine.push(nums[k]);
            dfs(n - 1, result, nums, currentCombine, target - nums[k], k + 1, end);
            currentCombine.pop();
        }
    }
}
